package pl.agh.convexhulltutor.algorithms;

import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Stack;

import pl.agh.convexhulltutor.gui.DrawPanel;
import pl.agh.convexhulltutor.structures.Line;
import pl.agh.convexhulltutor.structures.Point;

public class GrahamAlgorithm extends Algorithm {
	private DrawPanel drawPanel;
	private List<Point> points;
	private List<Line> lines;
	private Point initialPoint;
	private List<Point> sortedPoints;
	private Stack<Point> stack = new Stack<Point>();
	private int index = 2;

	public GrahamAlgorithm(DrawPanel drawPanel) {
		super(drawPanel);
		this.drawPanel = drawPanel;
	}

	private void sortPointsByAngles() {
		Collections.sort(points, new Comparator<Point>() {
			private double getAngle(Point commonPoint, Point lonePoint1,
					Point lonePoint2) {
				double dx21 = lonePoint1.getX() - commonPoint.getX();
				double dx31 = lonePoint2.getX() - commonPoint.getX();
				double dy21 = lonePoint1.getY() - commonPoint.getY();
				double dy31 = lonePoint2.getY() - commonPoint.getY();
				double m12 = Math.sqrt(dx21 * dx21 + dy21 * dy21);
				double m13 = Math.sqrt(dx31 * dx31 + dy31 * dy31);
				return Math.acos((dx21 * dx31 + dy21 * dy31) / (m12 * m13));
			}

			private double angleToSurface(Point commonPoint, Point point) {
				Point surfacePoint = new Point(drawPanel.getWidth() - 1,
						commonPoint.getY());
				return getAngle(commonPoint, surfacePoint, point);
			}

			@Override
			public int compare(Point p1, Point p2) {
				double angle1 = angleToSurface(initialPoint, p1);
				double angle2 = angleToSurface(initialPoint, p2);
				double myAngle = angle2 - angle1;
				double dist1 = Math.sqrt(Math.pow(
						initialPoint.getX() - p1.getX(), 2)
						+ Math.pow(initialPoint.getY() - p1.getY(), 2));
				double dist2 = Math.sqrt(Math.pow(
						initialPoint.getX() - p2.getX(), 2)
						+ Math.pow(initialPoint.getY() - p2.getY(), 2));
				return -(myAngle > 0.0 ? 1 : myAngle < 0.0 ? -1
						: dist1 > dist2 ? 1 : -1);
			}
		});
		sortedPoints = points;
	}

	private void push(Point point) {
		getUpdatedPoint(point, points).setColor(Point.CONVEX_HULL_COLOR);
		if (!stack.isEmpty()) {
			lines.add(new Line(stack.peek(), point, Line.CONVEX_HULL_COLOR));
		}
		stack.push(point);
	}

	private void pop() {
		Point point = stack.pop();
		getUpdatedPoint(point, points).setPreviousColor();
		lines.remove(lines.size() - 1);
	}

	@Override
	public void execute(List<Point> points, List<Line> lines) {
		this.points = points;
		this.lines = lines;
		if (currentStep == 1) {
			initialPoint = Collections.max(points, new Comparator<Point>() {
				@Override
				public int compare(Point p1, Point p2) {
					return p1.compareCoordinates(p2, false);
				}
			});
			sortPointsByAngles();
		} else if (currentStep - 1 < sortedPoints.size()) {
			lines.add(new Line(initialPoint, sortedPoints.get(currentStep - 2)));
		} else if (currentStep - 1 < sortedPoints.size() + 1) {
			push(initialPoint);
			push(sortedPoints.get(0));
			push(sortedPoints.get(1));
		} else if (currentStep - 1 < sortedPoints.size() + 1
				+ sortedPoints.size() - 3) {
			while (getDeterminantSign(stack.get(stack.size() - 1),
					stack.get(stack.size() - 2), sortedPoints.get(index)) <= 0.0) {
				pop();
			}
			push(sortedPoints.get(index));
			index++;
		} else {
			maxStep = currentStep;
			lines.add(new Line(initialPoint, stack.get(stack.size() - 1),
					Line.CONVEX_HULL_COLOR));
			for (Point point : points) {
				if (point.getColor() != Point.CONVEX_HULL_COLOR) {
					point.setColor(Point.NON_CONVEX_HULL_COLOR);
				}
			}
		}
	}
}
